package ljl.codetop300;

import commons.WrongAnswer;

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeSet;

public class _460_LFUCache {

  //["LFUCache","put","put","get","put","get","get","put","get","get","get"]
  //[[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
  //添加到测试用例
  //输出
  //[null,null,null,1,null,2,3,null,-1,3,4]
  //预期结果
  //[null,null,null,1,null,-1,3,null,-1,3,4]
  public static void main(String[] args) {
    LFUCache cache = new LFUCache(2);

    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1);
    cache.put(3, 3);
    System.out.println(cache.get(2));
    System.out.println(cache.get(1));
  }

  @WrongAnswer("我受不了啦")
  static class LFUCache {

    static class Entry {
      int key;
      int value;
      int count;
    }
    PriorityQueue<Entry> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.count));
    Map<Integer, Entry> map = new HashMap<>();
    int cap;
    int size;
    public LFUCache(int capacity) {
      cap = capacity;
    }

    public int get(int key) {
      if (map.containsKey(key)) {
        Entry entry = map.get(key);
        entry.count++;
        return entry.value;
      }
      return -1;
    }

    public void put(int key, int value) {
      if (map.containsKey(key)) {
        Entry entry = map.get(key);
        entry.count++;
        entry.value = value;
      } else {
        if (++size > cap) {
          Entry entry = queue.poll();
          map.remove(entry.key);
        }
        Entry entry = new Entry();
        entry.count = 1;
        entry.key = key;
        entry.value = value;
        map.put(key, entry);
        queue.offer(entry);
      }
    }
  }

  /**
   * 官方题解1：平衡二叉
   */
  static class LFUCache1 {
    // 缓存容量，时间戳
    int capacity, time;
    Map<Integer, Node> key_table = new HashMap<>();
    TreeSet<Node> S = new TreeSet<>();

    public LFUCache1(int capacity) {
      this.capacity = capacity;
    }

    public int get(int key) {
      if (capacity == 0) {
        return -1;
      }
      if (!key_table.containsKey(key)) {
        return -1;
      }
      Node cache = key_table.get(key);
      S.remove(cache);
      cache.cnt += 1;
      cache.time = ++time;
      // 将新缓存重新放入哈希表和平衡二叉树中
      S.add(cache);
      key_table.put(key, cache);
      return cache.value;
    }

    public void put(int key, int value) {
      if (capacity == 0) {
        return;
      }
      if (!key_table.containsKey(key)) {
        // 如果到达缓存容量上限
        if (key_table.size() == capacity) {
          // 从哈希表和平衡二叉树中删除最近最少使用的缓存
          key_table.remove(S.first().key);
          S.remove(S.first());
        }
        // 创建新的缓存
        Node cache = new Node(1, ++time, key, value);
        // 将新缓存放入哈希表和平衡二叉树中
        key_table.put(key, cache);
        S.add(cache);
      } else {
        // 这里和 get() 函数类似
        Node cache = key_table.get(key);
        S.remove(cache);
        cache.cnt += 1;
        cache.time = ++time;
        cache.value = value;
        S.add(cache);
        key_table.put(key, cache);
      }
    }
  }

  static class Node implements Comparable<Node> {
    int cnt, time, key, value;

    Node(int cnt, int time, int key, int value) {
      this.cnt = cnt;
      this.time = time;
      this.key = key;
      this.value = value;
    }

    public boolean equals(Object anObject) {
      if (this == anObject) {
        return true;
      }
      if (anObject instanceof Node) {
        Node rhs = (Node) anObject;
        return this.cnt == rhs.cnt && this.time == rhs.time;
      }
      return false;
    }

    public int compareTo(Node rhs) {
      return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt;
    }

    public int hashCode() {
      return cnt * 1000000007 + time;
    }
  }


  /**
   * 官方题解2：双哈希表
   */
  static class LFUCache2 {
    int minfreq;
    int capacity;
    Map<Integer, Node2> keyTable = new HashMap<>();
    Map<Integer, DoublyLinkedList> freqTable = new HashMap<>();

    public LFUCache2(int capacity) {
      this.capacity = capacity;
    }

    /**
     * 每次往里放，都会挪动这个节点
     * 然后放到 freq + 1 那个链表头部
     * 然后把 key table 的 value 设置成 它
     */
    public int get(int key) {
      if (!keyTable.containsKey(key)) {
        return -1;
      }
      Node2 node = keyTable.get(key);
      int val = node.val;
      int freq = node.freq;
      freqTable.get(freq).remove(node);
      // 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
      if (freqTable.get(freq).size == 0) {
        freqTable.remove(freq);
        if (minfreq == freq) {
          // 感觉这不太对，可能是 1 和 3，你这不成 2 了？不对，是它自己涨了，自己从 1 变成 2 了
          // 所以是 2，是对的
          minfreq += 1;
        }
      }
      // 插入到 freq + 1 中
      DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
      list.addFirst(new Node2(key, val, freq + 1));
      freqTable.put(freq + 1, list);
      keyTable.put(key, freqTable.get(freq + 1).getHead());
      return val;
    }

    public void put(int key, int value) {
      if (capacity == 0) {
        return;
      }
      if (!keyTable.containsKey(key)) {
        // 缓存已满，需要进行删除操作
        if (keyTable.size() == capacity) {
          // 通过 minFreq 拿到 freqTable[minFreq] 链表的末尾节点
          Node2 node = freqTable.get(minfreq).getTail();
          keyTable.remove(node.key);
          freqTable.get(minfreq).remove(node);
          if (freqTable.get(minfreq).size == 0) {
            freqTable.remove(minfreq);
          }
        }
        DoublyLinkedList list = freqTable.getOrDefault(1, new DoublyLinkedList());
        list.addFirst(new Node2(key, value, 1));
        freqTable.put(1, list);
        keyTable.put(key, freqTable.get(1).getHead());
        minfreq = 1;
      } else {
        // 与 get 操作基本一致，除了需要更新缓存的值
        Node2 node = keyTable.get(key);
        int freq = node.freq;
        freqTable.get(freq).remove(node);
        if (freqTable.get(freq).size == 0) {
          freqTable.remove(freq);
          if (minfreq == freq) {
            minfreq += 1;
          }
        }
        DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
        list.addFirst(new Node2(key, value, freq + 1));
        freqTable.put(freq + 1, list);
        keyTable.put(key, freqTable.get(freq + 1).getHead());
      }
    }
  }

  static class Node2 {
    int key, val, freq;
    Node2 prev, next;

    Node2() {
      this(-1, -1, 0);
    }

    Node2(int key, int val, int freq) {
      this.key = key;
      this.val = val;
      this.freq = freq;
    }
  }

  static class DoublyLinkedList {
    Node2 dummyHead, dummyTail;
    int size;

    DoublyLinkedList() {
      dummyHead = new Node2();
      dummyTail = new Node2();
      dummyHead.next = dummyTail;
      dummyTail.prev = dummyHead;
    }

    public void addFirst(Node2 node) {
      Node2 prevHead = dummyHead.next;
      node.prev = dummyHead;
      dummyHead.next = node;
      node.next = prevHead;
      prevHead.prev = node;
      size++;
    }

    public void remove(Node2 node) {
      Node2 prev = node.prev, next = node.next;
      prev.next = next;
      next.prev = prev;
      size--;
    }

    public Node2 getHead() {
      return dummyHead.next;
    }

    public Node2 getTail() {
      return dummyTail.prev;
    }
  }
}
